package ee.project.skiplist;

// BinarySearchTree class
//
// CONSTRUCTION: with a value at least as large as all others
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items

/**
 * Implements a deterministic skip list. Note that all "matching" is based on
 * the compareTo method.
 * 
 * @author Mark Allen Weiss
 */
public class DSL {
	/**
	 * Construct the DSL.
	 * 
	 * @param inf
	 *            the largest Comparable.
	 */
	public DSL(Comparable inf) {
		infinity = inf;
		bottom = new SkipNode(null);
		bottom.right = bottom.down = bottom;
		tail = new SkipNode(infinity);
		tail.right = tail;
		header = new SkipNode(infinity, tail, bottom);
	}

	/**
	 * Insert into the DSL.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void insert(Comparable x) {
		SkipNode current = header;

		bottom.element = x;
		while (current != bottom) {
			while (current.element.compareTo(x) < 0)
				current = current.right;

			// If gap size is 3 or at bottom level and
			// must insert, then promote middle element
			if (current.down.right.right.element.compareTo(current.element) < 0) {
				current.right = new SkipNode(current.element, current.right,
						current.down.right.right);
				current.element = current.down.right.element;
			} else
				current = current.down;
		}

		// Raise height of DSL if necessary
		if (header.right != tail)
			header = new SkipNode(infinity, tail, header);
	}

	/**
	 * Remove from the DSL. Unimplemented.
	 * 
	 * @param x
	 *            the item to remove.
	 */
	public void remove(Comparable x) {
		System.out.println("Sorry, remove unimplemented");
	}

	/**
	 * Find the smallest item in the DSL.
	 * 
	 * @return smallest item, or null if empty.
	 */
	public Comparable findMin() {
		if (isEmpty())
			return null;

		SkipNode current = header;
		while (current.down != bottom)
			current = current.down;

		return elementAt(current);
	}

	/**
	 * Find the largest item in the DSL.
	 * 
	 * @return the largest item, or null if empty.
	 */
	public Comparable findMax() {
		if (isEmpty())
			return null;

		SkipNode current = header;
		for (;;)
			if (current.right.right != tail)
				current = current.right;
			else if (current.down != bottom)
				current = current.down;
			else
				return elementAt(current);
	}

	/**
	 * Find an item in the DSL.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item, or null if not found.
	 */
	public Comparable find(Comparable x) {
		SkipNode current = header;

		bottom.element = x;
		for (;;)
			if (x.compareTo(current.element) < 0)
				current = current.down;
			else if (x.compareTo(current.element) > 0)
				current = current.right;
			else
				return elementAt(current);
	}

	/**
	 * Make the DSL logically empty.
	 */
	public void makeEmpty() {
		header.right = tail;
		header.down = bottom;
	}

	/**
	 * Test if the DSL is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return header.right == tail && header.down == bottom;
	}

	/**
	 * Internal method to get element field.
	 * 
	 * @param t
	 *            the node.
	 * @return the element field, or null if t is null.
	 */
	private Comparable elementAt(SkipNode t) {
		return t == bottom ? null : t.element;
	}

	/**
	 * Print the DSL.
	 */
	private void printList() {
		SkipNode current = header;

		while (current.down != bottom)
			;

		while (current.right != tail) {
			System.out.println(current.element);
			current = current.right;
		}
	}

	/** The DSL header. */
	private SkipNode header;
	private Comparable infinity;
	private SkipNode bottom = null;
	private SkipNode tail = null;

	// Test program
	public static void main(String[] args) {
		DSL t = new DSL(new Integer(100000000));
		final int NUMS = 40000;
		final int GAP = 37;

		System.out.println("Checking... (no more output means success)");

		int sum = 0;
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			sum++;
			t.insert(new Integer(i));
		}

		System.out.println("sum " + sum);

		if (NUMS < 40)
			t.printList();
		if (((Integer) (t.findMin())).intValue() != 1
				|| ((Integer) (t.findMax())).intValue() != NUMS - 1)
			System.out.println("FindMin or FindMax error!");

		for (int i = 1; i < NUMS; i++)
			if (((Integer) (t.find(new Integer(i)))).intValue() != i)
				System.out.println("Find error1!");
		if (t.find(new Integer(0)) != null)
			System.out.println("Find error2!");
		if (t.find(new Integer(NUMS + 10)) != null)
			System.out.println("Find error2!");
	}
}
